ABC375 E - 3 Team Division
解答見るまでに思ったこと
いくつかの戦略が考えられそう
i) 3チームへの分割を全て列挙する方法をベースにする？
難しそうappbird.icon
1. $ 3^{N}通りを列挙するのはしんどい
2. 仮に等しい分割を見つけたとして、すでに与えられた分割との近さ$ A_1, \cdots A_nはどう評価する？
一番近いものをどうやって探索する？
ii) 与えられた分割から始めた3チーム間での人員のやりとりをベースにする？
人員のやりとりは組み合わせも順番も考えないといけなくて爆発しそう
どう戦力差を埋めるかに重視して、出し入れする人員を求めたいけど
2チーム間ならまだしも、3チーム間なのが厄介
2チームごとに独立して考えて、あとでどうにかして結合するって方策は使えない
でも、すでに与えられた分割との近さは評価しやすそう
$ \sum_i B_i \leq 1500と小さい。
でも、どうやって部分問題に分割するんだろう？
$ 1人動かしたときには最適じゃないのに、$ 2人動かした時に最適になる可能性は十分にある。
あと、DP三つも持つの？どう更新するの？
最適性を考えると状態が行き来してごっちゃになってる感じがいかにもDPって感じがするappbird.icon
うまく部分問題に整理することで、状態を整理したいわね
解答
$ dp(i, x, y, z): 人$ 1, \cdots, iまでを動かせる時、チーム$ 1, 2, 3の強さを$ x, y, zとするために必要な最小人数
はぇ〜賢い....appbird.icon
そうか、「人数」を最小にしたいんだから$ dpの中身自体は人数になるよな
$ dp(y) = \min\{dp(x_1), \cdots,dp(x_m)\}
$ \minのおかげでdpの最小性が確保されている だから、最小にする型の$ dpを使う時は最小にしたいものを値に取るように設定しなくてはならない。
$ zの情報は$ i, x, yに対して一意に定まるので冗長
$ dp(i, x, y)だけ持てばOK
$ 100 \times 1500/3 \times 1500/3 = 25 \times 10^6程度
この状態の集約の仕方はどうやって思いつくのか....？ 状態の遷移であることはわかるappbird.icon まず、人$ 1, \cdots, iという制約が付いているのはなぜ？
チームの強さを$ (x, y)と定めた時、操作によっては2回以上巡ることができるが
チームの強さを$ (i, x, y)は高々1回しか巡れない
厳密に言えば、高々$ 1回巡れるようにしても状態への到達可能性には影響がない
十分に選択の自由さが確保されている
順序を固定しても到達できる状態には変化がない
ここで変化してしまうと、dpで求めた最小が本当に最小であるかがわからない
なぜ、チームの強さに沿ってDPするのか？
一番愚直な方法：チーム1,2,3にそれぞれ配属された人をそれぞれ状態に持たせる
これが一番遷移に対する「状態」としては自然だが、いくつか欠点が挙げられる。
$ dp(i, x, y, z): x, y, z\subset \{1, 2, \cdots, N\}
1. これではDPが持つべき空間の広さは相当にでかい
$ xが取りうる空間の大きさは$ 2^N通り
$ x, y, z全体としては$ (2^{N})^3通り
2. チームの強さが等しいかどうかの判定に$ O(N)かかってしまう
できれば直接的に強さを$ O(1)で比較しにかかりたい
ということで、チームの強さによって状態を代表させたい
チームの強さは全て列挙できる（$ \sum_i B_i \leq 1500）
DPするための配列の引数に求められる必要十分条件は何か？appbird.icon 問題によって設定された探索空間$ G = (S, T, f)が存在したとする。 ただし、$ f: S \to \Rは状態の評価関数
問題が、ある$ P \sub Sの中で、$ f(s)を最適化するような$ s \in Pを要求しているとしよう。
今回であれば、$ f(s)は「状態$ sに到達させるために移動させる最小人数」 $ S: 状態 / $ T: 遷移
動的計画法を適用するために設定する探索空間$ G_{dp} = (S', T', f)は、次の要件を満たしていなくてはならない？ 要するに、"計算しやすい"DPには次が求められる？
これは厳しすぎて、実は$ f: S \to S'なる写像が存在することを言えればそれで良いように思えるappbird.icon
3. $ G_{dp}で遷移できるような操作は$ Gでもできること
厳密には
任意の$ (s'_1, s'_2)\in T'に対して、逆像$ f^{-1}(\{s'_1\}), f^{-1}(\{s'_{2}\})を考える。
すると、$ f^{-1}(\{s'_1\}) \times f^{-1}(\{s'_{2}\}) \subset Tである。
4. $ Gで遷移できるような操作は$ G_{dp}でもできること
噛み砕けば
各状態を高々一度巡るだけでグラフ$ G_{dp}全体を見通すことができる（計算量の削減に貢献）
$ (i, x, y, z)から再度$ (i, x, y, z)へ到達し直せるようなことがないこと。
$ ()
任意のチームの割り当てに対して、それに対応するような引数$ (i, x, y, z)が存在すること。
3.
今回の問題設定のままだと上記三件を満たす写像（特に条件1.）を作り出すのは難しかったappbird.icon
だから、「人員を移動させる順序を固定した」問題を作って、有向非巡回であるような状況を作り出した。